/**
 * 面试题23：链表中环的入口节点
 * <p>
 * <ol>
 *   <li>链表中是否存在环？</li>
 *   <li>若存在环，找出环的入口节点</li>
 *   <li>若存在环，求环中节点数</li>
 * </ol>
 * 环中节点数比较好求，从环中任意节点如入口节点，开始遍历到再次回到此节点，即可得到环中节点数
 */
public class Offer_23 {
    /*
      思路：
      将链表分为两段：无环段长度为 a，环段长度为 b。
      当快慢指针相遇时，设慢指针走了 x 步，则快指针走了 2x 步
      那么 2x - x = kb （k为正整数）
      即 x = kb

      那么 慢指针再走 a 步，就可以恰好到达环的起点
      因为 x + a = a + kb
      正好够从起点出发，走一段无环（a），再走 k 圈环段

      此时在起点处设置一个指针 p，让 p 与慢指针 slow 一起走，
      走了 a 步后将会在环的起点处相遇，即得到环的起点
    */
    /**
     * 找出链表中环的入口
     * 
     * @param head
     * @return 如果链表中存在环，则返回环的入口节点；否则返回 null
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        // 快慢指针
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 快慢指针相遇，说明链表有环
            if (fast == slow) {
                // 此时 slow 距离环的起点的距离恰好是 a
                ListNode p = head;
                while (p != slow) {
                    slow = slow.next;
                    p = p.next;
                }
                // slow 与 p 相遇的位置一定是环的起点
                return slow;
            }
        }
        // 链表无环，返回 null
        return null;
    }
}
/*
    解释：为何慢指针第一圈走不完一定会和快指针相遇？
    第一步：快指针先进入环 
    第二步：当慢指针刚到达环的入口时，快指针此时在环中的某个位置(也可能此时相遇) 
    第三步：设此时快指针和慢指针距离为x（若在第二步相遇，则x = 0）； 
    第四步：设环的周长为n，那么看成快指针追赶慢指针，需要追赶 n-x； 
    第五步：快指针每次都追赶慢指针1个单位，设慢指针速度1/s，快指针2/s，那么追赶需要 (n-x)s 
    第六步：在n-x秒内，慢指针走了n-x单位，因为x>=0，则慢指针走的路程小于等于n，即走不完一圈就和快指针相遇
*/
